package code301_400.code70_80;

/**
 * 你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
 *
 * 输入：a = 2, b = [3]
 * 输出：8
 *
 * 输入：a = 2, b = [1,0]
 * 输出：1024
 *
 * 输入：a = 1, b = [4,3,3,8,5,2]
 * 输出：1
 */
public class _372superPow {

    /**
     * 本题解未考虑N次幂问题，只考虑到了求余的交换律，故未完成
     * @param a
     * @param b
     * @return
     */
    public static int superPow(int a, int[] b) {
        if(a==1)return 1;
        if(b.length==1&&b[0]==0)return 1;
        //powNum记录第几个幂大于1337
        int powNum = 1;
        // temp记录大于1337的余数
        int temp = a;
        if(temp<1337){
            while (temp<1337){
                temp = temp*a;
                powNum++;
            }
        }
        temp = temp%1337;
        int pow = 0;
        // pow记录指数个数
        if(b.length==1){
            pow = b[b.length-1];
        }else {
            for (int i = 0; i < b.length; i++) {
                pow = (int) (pow + b[b.length-1-i]*Math.pow(10,i));
            }
        }
        // 记录剩余多少指数
        int last;
        int lastPow;
        if(pow>powNum){
            last = pow/powNum;
            lastPow = pow%powNum;
            return (int)(Math.pow(a,lastPow)*(last*temp))%1337;
        }else {
            last = pow;
            return (int)Math.pow(a,last)%1337;
        }
    }

    public static void main(String[] args) {
        System.out.println(superPow(2147483647,new int[]{2,0,0}));
    }

    /**
     * 官方题解
     *
     * 执行用时：     * 5 ms     * , 在所有 Java 提交中击败了     * 57.14%     * 的用户
     * 内存消耗：     * 38.3 MB     * , 在所有 Java 提交中击败了     * 91.47%     * 的用户
     *
     */
    static final int MOD = 1337;

    public int superPow1(int a, int[] b) {
        int ans = 1;
        for (int e : b) {
            ans = (int) ((long) pow(ans, 10) * pow(a, e) % MOD);
        }
        return ans;
    }

    public int pow(int x, int n) {
        int res = 1;
        while (n != 0) {
            if (n % 2 != 0) {
                res = (int) ((long) res * x % MOD);
            }
            x = (int) ((long) x * x % MOD);
            n /= 2;
        }
        return res;
    }
}
